package com.zh.note.huawei.onehundred.最佳植树距离;

import java.util.Arrays;

/**
 * @Author: zhanghuan
 * @date: 2023/8/17 09:03
 * @description: create it
 */
public class Main {
    public static void main(String[] args) {
        // Scanner sc = new Scanner(System.in);
        // int n = sc.nextInt();
        // int[] holes = new int[n];
        // for (int i = 0; i < n; i++) {
        //     holes[i] = sc.nextInt();
        // }
        // int target = sc.nextInt();
        int n = 7;
        int[] holes = {1, 3, 6, 7, 8, 11, 13};
        int target = 3;


        int res = solution(holes, target);
        System.out.println(res);

    }

    private static int solution(int[] holes, int target) {
        Arrays.sort(holes);
        int left = 0;
        int right = holes[holes.length - 1];
        int res = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int count = 1;
            int pre = holes[0];
            for (int i = 1; i < holes.length; i++) {
                if (holes[i] - pre >= mid) {
                    count++;
                    pre = holes[i];
                    if (count >= target) {
                        res = mid;
                        left = mid + 1;
                        break;
                    }
                }
            }
            if (count < target) {
                right = mid - 1;
            }
        }
        return res;
    }
}
